import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
 class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int V = in.nextInt();

        int[] v = new int[n + 1];
        int[] w = new int[n + 1];


        for (int i = 1; i < n + 1; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        dp1(n,V,v,w);
        dp2(n,V,v,w);






    }


    private static void dp1(int n, int V, int[] v, int[] w) {
        int[] dp = new int[V+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                if (j >= v[i]) dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }


        }

        System.out.println(dp[V]);


    }



    private static void dp2(int n, int V, int[] v, int[] w) {
        int[] dp = new int[V + 1];


        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                if (j >= v[i]&&dp[j-v[i]]!=0||j==v[i]) dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }


        }

        System.out.println(dp[V]);

    }




}





class Solution {
    public int coinChange(int[] coins, int amount) {
        int n=coins.length;
        int[] dp=new int[amount+1];

        for(int i=1;i<=amount;i++) dp[i]=0x3f3f3f3f;

        for(int i=1;i<n+1;i++){
            for(int j=coins[i-1];j<amount+1;j++){
                dp[j]=Math.min(dp[j],dp[j-coins[i-1]]+1);
            }
        }

        return dp[amount]==0x3f3f3f3f?-1:dp[amount];

    }
}



class Solution2 {
    public int change(int amount, int[] coins) {
        int n=coins.length;
        int[] dp=new int[amount+1];


        dp[0]=1;

        for(int i=1;i<n+1;i++){
            for(int j=coins[i-1];j<amount+1;j++){
                dp[j]+=dp[j-coins[i-1]];
            }
        }

        return dp[amount];
    }
}


class Solution1 {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates); // 关键：排序以便剪枝
        backtrack(candidates, target, 0, 0);
        return result;
    }

    private void backtrack(int[] candidates, int target, int start, int sum) {
        if (sum == target) {
            result.add(new ArrayList<>(path)); // 找到合法组合
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            int newSum = sum + candidates[i];
            if (newSum > target) {
                break; // 剪枝：后续更大的数无需尝试
            }
            path.add(candidates[i]);
            backtrack(candidates, target, i, newSum); // 允许重复选当前数
            path.remove(path.size() - 1); // 回溯
        }
    }
}